λ¬Έμ
μΈμ²΄μ μΉλͺ μ μΈ λ°μ΄λ¬μ€λ₯Ό μ°κ΅¬νλ μ°κ΅¬μμμ λ°μ΄λ¬μ€κ° μ μΆλμλ€. λ€νν λ°μ΄λ¬μ€λ μμ§ νΌμ§μ§ μμκ³ , λ°μ΄λ¬μ€μ νμ°μ λ§κΈ° μν΄μ μ°κ΅¬μμ λ²½μ μΈμ°λ €κ³ νλ€. μ°κ΅¬μλ ν¬κΈ°κ° NΓMμΈ μ§μ¬κ°νμΌλ‘ λνλΌ μ μμΌλ©°, μ§μ¬κ°νμ 1Γ1 ν¬κΈ°μ μ μ¬κ°νμΌλ‘ λλμ΄μ Έ μλ€. μ°κ΅¬μλ λΉ μΉΈ, λ²½μΌλ‘ μ΄λ£¨μ΄μ Έ μμΌλ©°, λ²½μ μΉΈ νλλ₯Ό κ°λ μ°¨μ§νλ€. μΌλΆ μΉΈμ λ°μ΄λ¬μ€κ° μ‘΄μ¬νλ©°, μ΄ λ°μ΄λ¬μ€λ μνμ’μ°λ‘ μΈμ ν λΉ μΉΈμΌλ‘ λͺ¨λ νΌμ Έλκ° μ μλ€. μλ‘ μΈμΈ μ μλ λ²½μ κ°μλ 3κ°μ΄λ©°, κΌ 3κ°λ₯Ό μΈμμΌ νλ€. μλ₯Ό λ€μ΄, μλμ κ°μ΄ μ°κ΅¬μκ° μκΈ΄ κ²½μ°λ₯Ό μ΄ν΄λ³΄μ.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
μ΄λ, 0μ λΉ μΉΈ, 1μ λ²½, 2λ λ°μ΄λ¬μ€κ° μλ κ³³μ΄λ€. μλ¬΄λ° λ²½μ μΈμ°μ§ μλλ€λ©΄, λ°μ΄λ¬μ€λ λͺ¨λ λΉ μΉΈμΌλ‘ νΌμ Έλκ° μ μλ€. 2ν 1μ΄, 1ν 2μ΄, 4ν 6μ΄μ λ²½μ μΈμ΄λ€λ©΄ μ§λμ λͺ¨μμ μλμ κ°μμ§κ² λλ€.
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
λ°μ΄λ¬μ€κ° νΌμ§ λ€μ λͺ¨μ΅μ μλμ κ°μμ§λ€.
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
λ²½μ 3κ° μΈμ΄ λ€, λ°μ΄λ¬μ€κ° νΌμ§ μ μλ κ³³μ μμ μμμ΄λΌκ³ νλ€. μμ μ§λμμ μμ μμμ ν¬κΈ°λ 27μ΄λ€. μ°κ΅¬μμ μ§λκ° μ£Όμ΄μ‘μ λ μ»μ μ μλ μμ μμ ν¬κΈ°μ μ΅λκ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ , μΆλ ₯
μ λ ₯
- 첫째 μ€μ μ§λμ μΈλ‘ ν¬κΈ° Nκ³Ό κ°λ‘ ν¬κΈ° Mμ΄ μ£Όμ΄μ§λ€. (3 β€ N, M β€ 8)
- λμ§Έ μ€λΆν° Nκ°μ μ€μ μ§λμ λͺ¨μμ΄ μ£Όμ΄μ§λ€. 0μ λΉ μΉΈ, 1μ λ²½, 2λ λ°μ΄λ¬μ€κ° μλ μμΉμ΄λ€. 2μ κ°μλ 2λ³΄λ€ ν¬κ±°λ κ°κ³ , 10λ³΄λ€ μκ±°λ κ°μ μμ°μμ΄λ€.
- λΉ μΉΈμ κ°μλ 3κ° μ΄μμ΄λ€.
μΆλ ₯
- 첫째 μ€μ μ»μ μ μλ μμ μμμ μ΅λ ν¬κΈ°λ₯Ό μΆλ ₯νλ€.
π Logic
class Lab {
Queue<Loc> locQueue;
int N, M;
int safeArea = 0;
int[][] map;
int[][] copyMap;
int[] rangeX = { -1, 0, 1, 0 };
int[] rangeY = { 0, 1, 0, -1 };
Loc[] orgSafe;
int idx0 = 0;
...
}
- μ°κ΅¬μμ μ 보λ₯Ό κ΄λ¦¬νλ ν΄λμ€
- μλ³Έ μ°κ΅¬μ μ 보λ₯Ό μ μ₯νλ
mapκ³Ό λ°μ΄λ¬μ€λ₯Ό μ€μ λ‘ νΌλ¨λ¦΄copyMapμ μ¬μ©νλ€. - λν λ²½μ μΈμΈ 곡κ°λ€μ μ μ₯νλ
orgSafeλ°°μ΄μ μ¬μ©νλ€. setWall()μ¬κ· νΈμΆλ‘ λ²½μ μΈμ°κ³ , λ²½μ λ€ μΈμ΄ λ€μ,spreadVirus()μμ BFS λ°©μμΌλ‘ λ°μ΄λ¬μ€λ₯Ό νΌλ¨λ¦°λ€.- μ΄ν,
countAndReset()μΌλ‘ λ°μ΄λ¬μ€κ° νΌμ§ μ΄νμ μμ μμμ μΉ΄μ΄νΈνκ³ ,mapμ μ΄μ©ν΄copyMapμ λ°μ΄λ¬μ€κ° νΌμ§κΈ° μ μνλ‘ λλ €λλλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Loc {
int x, y;
public Loc(int x, int y) {
this.x = x;
this.y = y;
}
}
class Lab {
Queue<Loc> locQueue;
int N, M;
int safeArea = 0;
int[][] map;
int[][] copyMap;
int[] rangeX = { -1, 0, 1, 0 };
int[] rangeY = { 0, 1, 0, -1 };
Loc[] orgSafe;
int idx0 = 0;
public Lab (int N, int M) {
this.N = N;
this.M = M;
map = new int[N][M];
copyMap = new int[N][M];
orgSafe = new Loc[N*M];
locQueue = new LinkedList<>();
}
public int findMaxSafeArea() {
setWall(0,3);
return safeArea;
}
private void setWall(int idx, int count) {
if (count == 0) {
spreadVirus();
int result = countAndReset();
if (safeArea < result) safeArea = result;
} else {
count--;
for (int i = idx; i < idx0; i++) {
copyMap[orgSafe[i].x][orgSafe[i].y] = 1;
setWall(i + 1, count);
copyMap[orgSafe[i].x][orgSafe[i].y] = 0;
}
}
}
private void spreadVirus() {
for (int i = 0; i < locQueue.size(); i++) {
Loc tmpLoc = locQueue.poll();
bfs(tmpLoc.x, tmpLoc.y);
locQueue.add(tmpLoc);
}
}
private void bfs(int x, int y) {
Queue<Loc> queue = new LinkedList<>();
queue.add(new Loc(x, y));
while (!queue.isEmpty()){
Loc tmp = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = tmp.x + rangeX[i], ny = tmp.y + rangeY[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (copyMap[nx][ny] == 0) {
queue.add(new Loc(nx, ny));
copyMap[nx][ny] = 2;
}
}
}
}
private int countAndReset() {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copyMap[i][j] == 0) count++;
if (copyMap[i][j] == 2) {
if (locQueue.contains(new Loc(i, j))) continue;
copyMap[i][j] = map[i][j];
}
}
}
return count;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int M = Integer.parseInt(line[1]);
Lab lab = new Lab(N, M);
for (int i = 0; i < N; i++) {
lab.map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int j = 0; j < M; j++) {
if (lab.map[i][j] == 2)
lab.locQueue.add(new Loc(i, j));
else if (lab.map[i][j] == 0)
lab.orgSafe[lab.idx0++] = new Loc(i, j);
lab.copyMap[i][j] = lab.map[i][j];
}
}
br.close();
System.out.println(lab.findMaxSafeArea());
}
}
βοΈ Review
- μλμ μ°κ΅¬μ μ 보λ₯Ό κ°μ§νκΈ° μν΄
mapκ³ΌcopyMapλ°°μ΄μ λκ³ μ§ννλλ°, κ³μ λ λ°°μ΄μ΄ λκΈ°νλ κ²λ§λ₯ κ°μ΄ κ°μ΄ λ³κ²½λκ³ μμλ€. μ무λλlab.map[i] = lab.copyMap[i];μ΄ μ½λ λλ¬Έμ μΈμ€ν΄μ€μ μ£Όμ 곡μ λ μ°Έμ‘°μ λ¬Έμ μΌκ±°λΌ μκ°ν΄ κ²μν΄λ³΄λ μλλ λ€λ₯ΌκΉ "μμ 볡μ¬μ κΉμ 볡μ¬" λ¬Έμ μλ€. ν λ² μ 리ν΄μΌκ² λ€. - λ°μ΄λ¬μ€κ° νΌμ§ μ΄ν λ€μ μμ볡ꡬν λ, μΈμ΄ λ²½κΉμ§ μμ λ²λ¦¬λ μ΄κΈ°ν κ³Όμ λλ¬Έμ κ°μ΄ κ³μ μλͺ» λμλ€. μ΄κΈ°ν κ³Όμ μ νμ μ νμΈνμ.
π μΆμ²
Baekjoon : https://www.acmicpc.net/problem/14502